// 79.单词搜索

package LeetcodeHot100;

public class Solution079 {
    public boolean isExist = false;

    public boolean exist(char[][] board, String word) {
        boolean[][] isVisit = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    isVisit[i][j] = true;
                    BackTrace(board, word, 1, new int[] { i, j }, isVisit);
                    isVisit[i][j] = false;
                }
            }
        }
        return isExist;
    }

    private void BackTrace(char[][] board, String word, int cur, int[] location, boolean[][] isVisit) {
        if (cur == word.length()) {
            isExist = true;
            return;
        }
        if (cur > word.length())
            return;
        int x = location[0];
        int y = location[1];
        if (x - 1 >= 0 && board[x - 1][y] == word.charAt(cur) && isVisit[x - 1][y] == false) {
            isVisit[x - 1][y] = true;
            BackTrace(board, word, cur + 1, new int[] { x - 1, y }, isVisit);
            isVisit[x - 1][y] = false;
        }
        if (x + 1 < board.length && board[x + 1][y] == word.charAt(cur) && isVisit[x + 1][y] == false) {
            isVisit[x + 1][y] = true;
            BackTrace(board, word, cur + 1, new int[] { x + 1, y }, isVisit);
            isVisit[x + 1][y] = false;
        }
        if (y - 1 >= 0 && board[x][y - 1] == word.charAt(cur) && isVisit[x][y - 1] == false) {
            isVisit[x][y - 1] = true;
            BackTrace(board, word, cur + 1, new int[] { x, y - 1 }, isVisit);
            isVisit[x][y - 1] = false;
        }
        if (y + 1 < board[0].length && board[x][y + 1] == word.charAt(cur) && isVisit[x][y + 1] == false) {
            isVisit[x][y + 1] = true;
            BackTrace(board, word, cur + 1, new int[] { x, y + 1 }, isVisit);
            isVisit[x][y + 1] = false;
        }
    }
}
